//一元多项式的框架
public class polynomial {
    static class ListNode {
        //节点的成员
        public int index;       //幂
        public double val;      //系数
        public ListNode prev;
        public ListNode next;
        public ListNode(int index, double val) {
            this.index = index;
            this.val = val;
        }
    }
    public ListNode head1;
    public ListNode head2;
    public ListNode head = new ListNode(-1, 0);
    public void clear(ListNode head) {
        ListNode cur = head;
        while (cur != null) {
            ListNode curNext = cur.next;
            cur.next = null;
            cur.prev = null;
            cur = curNext;
        }
        head = null;
    }
    String order = "", rorder = "";    //输出格式的字符串
    //GET的功能将输入的字符串s表示的一元多项式解析，并根据指数的大小将其插入到链表中合适的位置。
//每个节点（ListNode）代表一个单项式，其中包含指数和系数。最后返回链表的头节点。
    public ListNode Get(String s, ListNode head, ListNode last) {
        int i = 0;                                      //用符号判断项，将项拆分
        while (i < s.length()) {
//// 检查符号，如果是减号则设置flag为-1，i加1；如果是加号则只将i加1
            int flag = 1;
            if (s.charAt(i) == '-') {
                flag = -1;
                i++;
            } else if (s.charAt(i) == '+') {
                i++;
            }
            //// 寻找"-"或"+"字符之前的数字部分
            int j = i;
            while (i < s.length() && "+-".indexOf(s.charAt(i)) == -1) {
                i++;
            }
            //// 寻找"x"字符的位置
            int k = j;
            while (k < i && s.charAt(k) != 'x') {
                k++;
            }
            //// 找系数
            int n = 0;
            if (k == i) {
                n = 0;//// 系数为0
            } else if (k + 1 == i) {
                n = 1;//// 系数为1
            } else {            //？？
                n = Integer.parseInt(s.substring(k + 2, i));    //提取x后面的系数
            }
            double val = 1;
            if (j != k)         //？？
                val = Double.parseDouble(s.substring(j, k)) * flag;     //// 提取数字部分并乘以符号flag
            // // 链表为空，则创建新的节点作为头节点并赋值给head和last
            if (head == null) {
                ListNode newnode = new ListNode(n, val);
                head = last = newnode;
                continue;
            }
            for (ListNode cur = head; cur != null; cur = cur.next) {
                if (cur.index == n) {
///// 如果当前节点的指数与新节点的指数相同，则将新节点的值加到当前节点的值上
                    cur.val += val;
                    break;
                }
                if (cur.index > n) {
//// 如果当前节点的指数大于新节点的指数，则将新节点插入当前节点之前
                    ListNode newnode = new ListNode(n, val);
                    newnode.next = cur;
                    newnode.prev = cur.prev;
                    if (cur == head)
                        head = newnode;
                    else
                        cur.prev.next = newnode;
                    cur.prev = newnode;
                    break;
                }
                if (cur.next == null) {
//// 如果遍历到最后一个节点，则将新节点插入到最后
                    ListNode newnode = new ListNode(n, val);
                    newnode.prev = last;
                    last.next = newnode;
                    last = last.next;
                    break;
                }
            }
        }
        return head;
    }
    //多项式的+、-、*，运算
    polynomial(char op, String x, String y) {
        head1 = Get(x, head1, null);        //用Get处理两表达式
        head2 = Get(y, head2, null);
        ListNode cur1 = head1, cur2 = head2, cur = head;
        if (op == '-') {
            while (cur1 != null && cur2 != null) {
                if (cur1.index == cur2.index) {
                    //// 如果两个多项式节点的指数相同，则将它们的系数相减，并创建新的节点储存结果
                    ListNode newnode = new ListNode(cur1.index, cur1.val - cur2.val);
                    cur.next = newnode;
                    newnode.prev = cur;
                    cur = cur.next;
                    cur1 = cur1.next;
                    cur2 = cur2.next;
                } else if (cur1.index < cur2.index) {
                    //// 如果第一个多项式节点的指数小于第二个多项式节点的指数，则直接将第一个多项式节点插入到结果多项式中
                    ListNode newnode = new ListNode(cur1.index, cur1.val);
                    cur.next = newnode;
                    newnode.prev = cur;
                    cur = cur.next;
                    cur1 = cur1.next;
                } else {
                    // // 如果第一个多项式节点的指数大于第二个多项式节点的指数，则直接将第二个多项式节点插入到结果多项式中
                    ListNode newnode = new ListNode(cur2.index, -cur2.val);
                    cur.next = newnode;
                    newnode.prev = cur;
                    cur = cur.next;
                    cur2 = cur2.next;
                }
            }
            //// 将剩余的多项式节点插入到结果多项式中
            while (cur1 != null) {
                ListNode newnode = new ListNode(cur1.index, cur1.val);
                newnode.prev = cur;
                cur.next = newnode;
                cur = cur.next;
                cur1 = cur1.next;
            }
            while (cur2 != null) {
                ListNode newnode = new ListNode(cur2.index, -cur2.val);
                newnode.prev = cur;
                cur.next = newnode;
                cur = cur.next;
                cur2 = cur2.next;
            }
        } else if (op == '+') {
            while (cur1 != null && cur2 != null) {
                if (cur1.index == cur2.index) {
                    ListNode newnode = new ListNode(cur1.index, cur1.val + cur2.val);
                    cur.next = newnode;
                    newnode.prev = cur;
                    cur = cur.next;
                    cur1 = cur1.next;
                    cur2 = cur2.next;
                } else if (cur1.index < cur2.index) {
                    ListNode newnode = new ListNode(cur1.index, cur1.val);
                    cur.next = newnode;
                    newnode.prev = cur;
                    cur = cur.next;
                    cur1 = cur1.next;
                } else {
                    ListNode newnode = new ListNode(cur2.index, cur2.val);
                    cur.next = newnode;
                    newnode.prev = cur;
                    cur = cur.next;
                    cur2 = cur2.next;
                }
            }
            while (cur1 != null) {
                ListNode newnode = new ListNode(cur1.index, cur1.val);
                newnode.prev = cur;
                cur.next = newnode;
                cur = cur.next;
                cur1 = cur1.next;
            }
            while (cur2 != null) {
                ListNode newnode = new ListNode(cur2.index, cur2.val);
                newnode.prev = cur;
                cur.next = newnode;
                cur = cur.next;
                cur2 = cur2.next;
            }
        } else {
//双重循环遍历 head1 和 head2 的所有节点，相乘每对节点的系数并相加指数，然后将乘积作为新节点的
//系数，按照指数的大小将新节点插入结果多项式链表的适当位置
            for (cur1 = head1; cur1 != null; cur1 = cur1.next) {
                for (cur2 = head2; cur2 != null; cur2 = cur2.next) {
                    int index = cur1.index + cur2.index;        //指数相加
                    double val = cur1.val * cur2.val;           //系数相乘
                    //// 将新节点插入结果多项式链表中的合适位置
                    for (cur = head; cur != null; cur = cur.next) {
                        if (cur.index == index) {
                            cur.val += val;         //// 若当前节点的指数和新节点的指数相同，则将系数相加
                            break;
                        }
                        //大于放到前面
                        if (cur.index > index) {
                            ListNode newnode = new ListNode(index, val);
                            newnode.next = cur;
                            newnode.prev = cur.prev;
                            if (head == cur)
                                head = newnode;
                            else
                                cur.prev.next = newnode;
                            cur.prev = newnode;
                            break;
                        }
                        if (cur.next == null) {
                            ListNode newnode = new ListNode(index, val);
                            newnode.prev = cur;
                            cur.next = newnode;
                            cur = cur.next;
                            break;
                        }
                    }
                }
            }
        }
        clear(head1);       //清空链表
        clear(head2);
        ListNode last = null;   //// 声明一个变量 last，用于保存最后一个非零系数的节点
        //// 遍历结果多项式链表，生成结果多项式的字符串表达式
        for (cur = head.next; cur != null; last = cur, cur = cur.next) {
            if (cur.val == 0) continue;     //如果节点系数为零，跳过此节点
            //// 生成节点的表达式，并根据系数的正负和指数是否为零进行拼接
            order = order + (cur.val > 0 ? "+" : "") + cur.val + (cur.index == 0 ? "" : "x^" + cur.index);
        }
//// 如果结果多项式的字符串表达式为空，则将其设置为 "0"，并返回结果多项式和反序结果多项式的字符串表达式
        if (order == "") {
            order = "0";
            return;
        }
        //// 生成反序结果多项式的字符串表达式
        for (cur = last; cur != head; cur = cur.prev) {
            if (cur.val == 0) continue;     //// 如果节点系数为零，跳过此节点
// // 生成节点的表达式，并根据系数的正负和指数是否为零进行拼接
            rorder = rorder + (cur.val > 0 ? "+" : "") + cur.val + (cur.index == 0 ? "" : "x^" + cur.index);
        }
    }

    public static void main(String[] args) {
        polynomial a = new polynomial('+',"x^10+x^5","10x^4-x^5");
        System.out.println(a.order);
    }
}